package com.practice.sequence;

/**
 * Given a sequence of integer, each one is +1 or -1 of previous element.
 * Write a program to detect whether a given number target exists in
 * this sequence. (A)
 */
public class FindInRange {
	public boolean find(int[] a, int target) {
		return find(a, target, 0, a.length-1);
	}
	
	public boolean find(int[] a, int target, int lower, int upper) { 
		int low = Math.min(a[lower], a[upper]);
		int high = Math.max(a[lower], a[upper]);
		if (low <= target && high >= target) return true;
		
		int N = upper - lower;
		int lowestPossible = (low + high - N)/2;
		int highestPossible = (low + high + N)/2;
		if (target > highestPossible || target < lowestPossible) return false;
		
		return find(a, target, lower+1, (lower+upper)/2) ||
				find(a, target, (lower+upper)/2, upper-1);
	}
	
	public boolean exist(int A[], int target) {
	    int n = A.length;
		int i = 0;
	    int j = n-1;
	    while (i <= j) {
	        int left = A[i];
	        int right = A[j];
	        int diff1 = Math.abs(target - left);
	        int diff2 = Math.abs(target - right);
	        if (diff1 == 0 || diff2 == 0) {
	            return true;
	        } else {
	            i += diff1;
	            j -= diff2;
	        }
	    }
	    return false;
	}
}
